#include <stdio.h>
#include <stdbool.h>
#include <math.h>

bool is_prime(int num)
{
    if (num <= 1)
    {
        return false;
    }
    for (int i = 2; i <= sqrt(num); i++)
    {
        if (num % i == 0)
        {
            return false;
        }
    }
    return true;
}


void backtrack(int current[], bool visited[], int n, int depth, int result[][20], int *result_count)
{
    if (depth == n)
    {
        // 检查最后一个数字与第一个数字是否满足质数条件
        if (is_prime(current[n - 1] + current[0]))
        {
            // 存储一个有效的排列
            for (int i = 0; i < n; i++)
            {
                result[*result_count][i] = current[i];
            }
            (*result_count)++;
        }
        return;
    }

    for (int num = 2; num <= n; num++)
    {
        if (!visited[num] && is_prime(current[depth - 1] + num))
        {
            visited[num] = true;
            current[depth] = num;
            backtrack(current, visited, n, depth + 1, result, result_count);
            visited[num] = false; // 回溯
        }
    }
}

// 主函数
void solve(int n)
{
    int result[100][20];  // 用来存储符合条件的排列
    int result_count = 0;
    bool visited[n + 1];  // 标记哪些数字已经使用
    int current[n];  // 当前排列

    // 初始时，1已经放置在第一个位置
    for (int i = 0; i <= n; i++)
    {
        visited[i] = false;
    }
    visited[1] = true;
    current[0] = 1;

    // 调用回溯函数
    backtrack(current, visited, n, 1, result, &result_count);

    // 输出结果
    for (int i = 0; i < result_count; i++)
    {
        for (int j = 0; j < n; j++)
        {
            printf("%d ", result[i][j]);
        }
        printf("\n");
    }
}

// 输入处理
int main()
{
    int n;
    scanf("%d", &n);
    solve(n);
    return 0;
}
